#include <iostream>
#include <vector>
using namespace std;

void update_max(vector<vector<vector<int> > > &dp, int i, int j, int k, int val) {
    dp.at(i).at(j).at(k) = max(dp.at(i).at(j).at(k), val);
}

int get_seg_sum(vector<int> &suffix_sum, int i, int j)
{
    i++, j++;
    return suffix_sum[j] - suffix_sum[i - 1];
}
int get_seg_after_idx(vector<int> &suffix_sum, int idx, int seg_len)
{
    int res = get_seg_sum(suffix_sum, idx + 1, idx + seg_len);
    // console.log('get_seg_after_idx', idx, seg_len, res);
    return res;
}

void print_dp(vector<vector<vector<int> > > &dp, int nums_len, int k)
{
    for (int i = 0; i < nums_len+1; i++)
    {
        for (int j = 0; j < k+1; j++)
        {
            if (dp[i][j][0] == INT_MIN/2)
                cout << "inf";
            else
                cout << dp[i][j][0];
            cout << "/";
            if (dp[i][j][1] == INT_MIN/2)
                cout << "inf";
            else
                cout << dp[i][j][1];
            cout << "\t";
        }
        cout << endl;
    }
}

int maxSum(const vector<int>& nums, int k, int m) {
    int nums_len = nums.size();
    vector<int> suffix_sum(nums_len + 1, 0);
    for (int i = 1; i <= nums_len; ++i) {
        suffix_sum[i] = suffix_sum[i - 1] + nums[i - 1];
    }

    // 初始化dp数组
    vector<vector<vector<int> > > dp(nums_len + 1, 
        vector<vector<int> >(k + 1, 
            vector<int>(2, INT_MIN / 2)));

    for (int i = 0; i < nums_len; ++i) {
        dp[i][0][0] = 0;
        if (i >= m - 1) {
            dp[i][1][1] = get_seg_after_idx(suffix_sum, i-(m-1)-1, m);
        }
    }
    print_dp(dp, nums_len, k);

    vector<int> max_jSeg_sum_arr(k + 1, INT_MIN / 2);

    for (int i = 0; i < nums_len; ++i) {
        for (int j = 0; j <= k; ++j) {
            if (max_jSeg_sum_arr[j] != INT_MIN / 2) {
                update_max(dp, i, j, 0, max_jSeg_sum_arr[j]);
            }
            int cur_max = max(dp[i][j][0], dp[i][j][1]);
            if (cur_max == INT_MIN / 2) continue;
            max_jSeg_sum_arr[j] = max(max_jSeg_sum_arr[j], cur_max);

            if (j + 1 <= k && i + m < nums_len) {
                int sum_val = cur_max + get_seg_after_idx(suffix_sum, i, m);
                update_max(dp, i + m, j + 1, 1, sum_val);
                if (i + m + 1 < nums_len) {
                    update_max(dp, i + m + 1, j + 1, 0, sum_val);
                }
            }
            if (dp[i][j][1] != INT_MIN / 2 && i + 1 < nums_len) {
                update_max(dp, i + 1, j, 1, dp[i][j][1] + nums[i+1]);
            }
        }
    }

    print_dp(dp, nums_len, k);
    
    int max_ret = INT_MIN / 2;
    for (int i = 0; i < nums_len; ++i) {
        max_ret = max({max_ret, dp[i][k][0], dp[i][k][1]});
    }
    cout << "max_ret:\t" << max_ret << endl;
    return max_ret;
}

int main() {
    maxSum({1,2,-1,3,3,4}, 2, 2);
    maxSum({-10,3,-1,-2}, 4, 1);
    return 0;
}
